{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Kth Smallest Product of Two Sorted Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kthSmallestProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个有序数组的第 K 小乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你两个 <strong>从小到大排好序</strong>&nbsp;且下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;以及一个整数&nbsp;<code>k</code>&nbsp;，请你返回第<em>&nbsp;</em><code>k</code>&nbsp;（从 <strong>1</strong>&nbsp;开始编号）小的&nbsp;<code>nums1[i] * nums2[j]</code><em>&nbsp;</em>的乘积，其中<em>&nbsp;</em><code>0 &lt;= i &lt; nums1.length</code><em> </em>且<em> </em><code>0 &lt;= j &lt; nums2.length</code>&nbsp;。\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [2,5], nums2 = [3,4], k = 2\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>第 2 小的乘积计算如下：\n",
    "- nums1[0] * nums2[0] = 2 * 3 = 6\n",
    "- nums1[0] * nums2[1] = 2 * 4 = 8\n",
    "第 2 小的乘积为 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>第 6 小的乘积计算如下：\n",
    "- nums1[0] * nums2[1] = (-4) * 4 = -16\n",
    "- nums1[0] * nums2[0] = (-4) * 2 = -8\n",
    "- nums1[1] * nums2[1] = (-2) * 4 = -8\n",
    "- nums1[1] * nums2[0] = (-2) * 2 = -4\n",
    "- nums1[2] * nums2[0] = 0 * 2 = 0\n",
    "- nums1[2] * nums2[1] = 0 * 4 = 0\n",
    "第 6 小的乘积为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3\n",
    "<b>输出：</b>-6\n",
    "<b>解释：</b>第 3 小的乘积计算如下：\n",
    "- nums1[0] * nums2[4] = (-2) * 5 = -10\n",
    "- nums1[0] * nums2[3] = (-2) * 4 = -8\n",
    "- nums1[4] * nums2[0] = 2 * (-3) = -6\n",
    "第 3 小的乘积为 -6 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums1.length, nums2.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= nums1[i], nums2[j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums1.length * nums2.length</code></li>\n",
    "\t<li><code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;都是从小到大排好序的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [kth-smallest-product-of-two-sorted-arrays](https://leetcode.cn/problems/kth-smallest-product-of-two-sorted-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [kth-smallest-product-of-two-sorted-arrays](https://leetcode.cn/problems/kth-smallest-product-of-two-sorted-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5]\\n[3,4]\\n2', '[-4,-2,0,3]\\n[2,4]\\n6', '[-2,-1,0,1,2]\\n[-3,-1,2,4,5]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        def check(tgt):\n",
    "            cnt = 0\n",
    "            for num in nums2:\n",
    "                if num>0: # 正好等于tgt/num的也要算在内，因此用bisect_right\n",
    "                    cnt+=bisect_right(nums1,tgt/num)\n",
    "                elif num==0: # 除以0会RE，直接特判\n",
    "                    cnt+=len(nums1)*(tgt>=0) \n",
    "                else: # 注意此时用bisect_left，否则正好等于tgt/num的会被排除掉\n",
    "                    cnt+=len(nums1)-bisect_left(nums1,tgt/num)\n",
    "            return cnt\n",
    "        \n",
    "        mx = max(abs(nums1[0]),abs(nums1[-1]))*max(abs(nums2[0]),abs(nums2[-1])) #确定答案的可能范围\n",
    "        return bisect_left(range(-mx,mx+1),k,key=check)-mx #bisect_left输出的是下标，由于起点不是0，返回时要补差价\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        def check(tgt):\n",
    "            cnt = 0\n",
    "            for num in nums2:\n",
    "                if num>0: # 正好等于tgt/num的也要算在内，因此用bisect_right\n",
    "                    cnt+=bisect_right(nums1,tgt/num)\n",
    "                elif num==0: # 除以0会RE，直接特判\n",
    "                    cnt+=len(nums1)*(tgt>=0) \n",
    "                else: # 注意此时用bisect_left，否则正好等于tgt/num的会被排除掉\n",
    "                    cnt+=len(nums1)-bisect_left(nums1,tgt/num)\n",
    "            return cnt\n",
    "        \n",
    "        mx = max(abs(nums1[0]),abs(nums1[-1]))*max(abs(nums2[0]),abs(nums2[-1])) #确定答案的可能范围\n",
    "        return bisect_left(range(-mx,mx+1),k,key=check)-mx #bisect_left输出的是下标，由于起点不是0，返回时要补差价"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "    n, m = len(nums1), len(nums2)\n",
    "    \n",
    "    def CountLessThan(upto: int):\n",
    "      got = 0\n",
    "      for x in nums1:\n",
    "        if x > 0:\n",
    "          got += bisect_right(nums2, upto // x)\n",
    "          # got += bisect_right(nums2, floor(upto // x))\n",
    "        elif x < 0:\n",
    "          # got += m - bisect_left(nums2, (upto + x - 1) // x)\n",
    "          got += m - bisect_left(nums2, ceil(upto / x))\n",
    "        else:\n",
    "          got += 0 if upto < 0 else m\n",
    "      return got\n",
    "    \n",
    "    low, high = int(-1E10), int(1E10)\n",
    "    while low < high:\n",
    "      mid = (low + high) >> 1\n",
    "      got = CountLessThan(mid)\n",
    "      if got < k:\n",
    "        low = mid + 1\n",
    "      else:\n",
    "        high = mid\n",
    "    return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        p10 = bisect_left(nums1, 0)\n",
    "        p11 = bisect_left(nums1, 1)\n",
    "        p20 = bisect_left(nums2, 0)\n",
    "        p21 = bisect_left(nums2, 1)\n",
    "\n",
    "        neg = p10*(n2 - p21) + p20*(n1 - p11)\n",
    "        pos = p10*p20 + (n1-p11)*(n2-p21)\n",
    "        zero = n1*n2 - neg - pos\n",
    "        pos1, pos2 = nums1[p11:], nums2[p21:]\n",
    "        neg1, neg2 = nums1[:p10], nums2[:p20]\n",
    "        if k <= neg:\n",
    "            def check(p):\n",
    "                tot = 0\n",
    "                for x in neg1:\n",
    "                    tot += len(pos2) - bisect_left(pos2, (p+x+1)//x)\n",
    "                for x in neg2:\n",
    "                    tot += len(pos1) - bisect_left(pos1, (p+x+1)//x)\n",
    "                # print(\"tot\", tot)\n",
    "                return tot < k\n",
    "            left = -10**10\n",
    "            right = 0\n",
    "            while left <= right:\n",
    "                mid = (left + right)//2\n",
    "                # print(\"left, right, mid = \",left, right, mid)\n",
    "                if check(mid):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        if k <= neg + zero:\n",
    "            return 0\n",
    "        k -= neg + zero\n",
    "        left = 0\n",
    "        right = 10**10\n",
    "        def check(p):\n",
    "            tot = 0\n",
    "            for x in pos1:\n",
    "                tot += bisect_right(pos2, p//x)\n",
    "            for x in neg1:\n",
    "                tot += len(neg2) - bisect_left(neg2, (p+x+1)//x)\n",
    "            # print(\"tot\", tot)\n",
    "            return tot < k\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            # print(\"left, right, mid = \",left, right, mid)\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "    n, m = len(nums1), len(nums2)\n",
    "    \n",
    "    def CountLessThan(upto: int):\n",
    "      got = 0\n",
    "      for x in nums1:\n",
    "        if x > 0:\n",
    "          # got += bisect_right(nums2, upto // x)\n",
    "          got += bisect_right(nums2, floor(upto // x))\n",
    "        elif x < 0:\n",
    "          # got += m - bisect_left(nums2, (upto + x - 1) // x)\n",
    "          got += m - bisect_left(nums2, ceil(upto / x))\n",
    "        else:\n",
    "          got += 0 if upto < 0 else m\n",
    "      return got\n",
    "    \n",
    "    low, high = int(-1E10), int(1E10)\n",
    "    while low < high:\n",
    "      mid = (low + high) >> 1\n",
    "      got = CountLessThan(mid)\n",
    "      if got < k:\n",
    "        low = mid + 1\n",
    "      else:\n",
    "        high = mid\n",
    "    return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if len(nums1) >= len(nums2):\n",
    "            nums1, nums2 = nums2, nums1\n",
    "        a, b, c, d = nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[-1], nums1[-1] * nums2[0]\n",
    "        mn, mx = min(a, b, c, d), max(a, b, c, d)\n",
    "        while mn < mx:\n",
    "            mid = (mn + mx) >> 1\n",
    "            cnt = 0\n",
    "            for num in nums1:\n",
    "                if num > 0:\n",
    "                    cnt += bisect.bisect_right(nums2, mid // num)\n",
    "                elif num == 0:\n",
    "                    cnt += len(nums2) if mid >= 0 else 0\n",
    "                else:\n",
    "                    cnt += len(nums2) - bisect.bisect_left(nums2, math.ceil(mid / num))\n",
    "            if cnt < k:\n",
    "                mn = mid + 1\n",
    "            else:\n",
    "                mx = mid\n",
    "        return mn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, a: List[int], b: List[int], k: int) -> int:\n",
    "        # if len(a)>len(b):\n",
    "        #     return self.kthSmallestProduct(b, a, k)\n",
    "        def check(v):\n",
    "            res = 0\n",
    "            for x in a:\n",
    "                if x>0:\n",
    "                    res += bisect_right(b, v//x)\n",
    "                elif x<0:\n",
    "                    res += len(b)-bisect_left(b, ceil(v/x))\n",
    "                else:\n",
    "                    if v>=0:\n",
    "                        res += len(b)\n",
    "            return res>=k\n",
    "        mn = min(a[0]*b[0], a[0]*b[-1], a[-1]*b[0], a[-1]*b[-1])\n",
    "        mx = max(a[0]*b[0], a[0]*b[-1], a[-1]*b[0], a[-1]*b[-1])\n",
    "        left, right = -10**10-1, 10**10+1\n",
    "        while left+1 != right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        def get_info(L):\n",
    "            n = len(L)\n",
    "            zero_count = L.count(0)\n",
    "            if L[0] >= 0:\n",
    "                return 0, zero_count, n - zero_count, n \n",
    "            left = 0\n",
    "            right = len(L) - 1\n",
    "            while left < right:\n",
    "                middle = (left + right + 1) // 2\n",
    "                if L[middle] >= 0:\n",
    "                    right = middle - 1\n",
    "                else:\n",
    "                    left = middle\n",
    "            fu_count = left + 1\n",
    "            return fu_count, zero_count, n - fu_count - zero_count, n\n",
    "\n",
    "        fu_count1, zero_count1, zheng_count1, n1 = get_info(nums1)\n",
    "        fu_count2, zero_count2, zheng_count2, n2 = get_info(nums2)\n",
    "        fu_count = fu_count1 * zheng_count2 + fu_count2 * zheng_count1\n",
    "        zero_count = zero_count1 * n2 + zero_count2 * n1 - zero_count1 * zero_count2\n",
    "        min_value = min(nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[0], nums1[-1] * nums2[-1])\n",
    "        max_value = max(nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[0], nums1[-1] * nums2[-1])\n",
    "        def check(aim):\n",
    "            res = 0\n",
    "            if aim == 0:\n",
    "                return fu_count + zero_count\n",
    "            elif aim < 0:\n",
    "                res = 0\n",
    "                if fu_count1 > 0 and zheng_count2 > 0:\n",
    "                    idx1 = 0\n",
    "                    idx2 = fu_count2 + zero_count2\n",
    "                    while idx1 <= fu_count1 - 1 and idx2 < n2:\n",
    "                        if nums1[idx1] * nums2[idx2] > aim:\n",
    "                            idx2 += 1\n",
    "                        else:\n",
    "                            res += n2 - idx2\n",
    "                            idx1 += 1\n",
    "                if fu_count2 > 0 and zheng_count1 > 0:\n",
    "                    idx1 = fu_count1 + zero_count1\n",
    "                    idx2 = 0\n",
    "                    while idx1 < n1 and idx2 <= fu_count2 - 1:\n",
    "                        if nums1[idx1] * nums2[idx2] > aim:\n",
    "                            idx1 += 1\n",
    "                        else:\n",
    "                            res += n1 - idx1\n",
    "                            idx2 += 1\n",
    "                return res\n",
    "            else:\n",
    "                res = 0\n",
    "                if zheng_count1 > 0 and zheng_count2 > 0:\n",
    "                    idx1 = fu_count1 + zero_count1\n",
    "                    idx2 = n2 - 1\n",
    "                    while idx1 < n1 and idx2 >= fu_count2 + zero_count2:\n",
    "                        if nums1[idx1] * nums2[idx2] > aim:\n",
    "                            idx2 -= 1\n",
    "                        else:\n",
    "                            res += idx2 - fu_count2 - zero_count2 + 1\n",
    "                            idx1 += 1\n",
    "                if fu_count1 > 0 and fu_count2 > 0:\n",
    "                    idx1 = fu_count1 - 1\n",
    "                    idx2 = 0\n",
    "                    while idx1 >= 0 and idx2 <= fu_count2 - 1:\n",
    "                        if nums1[idx1] * nums2[idx2] > aim:\n",
    "                            idx2 += 1\n",
    "                        else:\n",
    "                            res += fu_count2 - idx2\n",
    "                            idx1 -= 1\n",
    "                return res + fu_count + zero_count\n",
    "                \n",
    "        \n",
    "        left = min_value\n",
    "        right = max_value\n",
    "        while left < right:\n",
    "            middle = (left + right) // 2\n",
    "            if check(middle) >= k:\n",
    "                right = middle\n",
    "            else:\n",
    "                left = middle + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pos = []\n",
    "        neg = []\n",
    "        for n in nums2:\n",
    "            if n >= 0:\n",
    "                pos.append(n)\n",
    "            else:\n",
    "                neg.append(n)\n",
    "        left = min(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                   nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        right = max(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                    nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        while left < right:\n",
    "            used = 0\n",
    "            mid = (left+right)//2\n",
    "            for n in nums1:\n",
    "                if n > 0:\n",
    "                    used += bisect_right(pos, mid//n)\n",
    "                    used += bisect_right(neg, mid//n)\n",
    "                elif n < 0:\n",
    "                    used += len(pos)-bisect_left(pos, mid //\n",
    "                                                 n+(1 if mid % n else 0))\n",
    "                    used += len(neg)-bisect_left(neg, mid //\n",
    "                                                 n+(1 if mid % n else 0))\n",
    "                else:\n",
    "                    if mid >= 0:\n",
    "                        used += len(pos)+len(neg)\n",
    "                    else:\n",
    "                        used += 0\n",
    "                if used >= k:\n",
    "                    break\n",
    "            if used < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        t = (nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[0], nums1[-1] * nums2[-1])\n",
    "        left, right = min(t), max(t)\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        neg1, pos1 = bisect_left(nums1, 0) - 1, bisect_left(nums1, 1)\n",
    "        neg2, pos2 = bisect_left(nums2, 0) - 1, bisect_left(nums2, 1)\n",
    "        cnt1, cnt2 = pos1 - neg1 - 1, pos2 - neg2 - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            cnt = cnt1 * n2 + (n1 - cnt1) * cnt2 if mid > 0 else 0\n",
    "            if mid >= 0:\n",
    "                cnt += (neg1 + 1) * (n2 - pos2) + (n1 - pos1) * (neg2 + 1)\n",
    "                j = neg2\n",
    "                for x in nums1[:neg1 + 1]:\n",
    "                    while j >= 0 and x * nums2[j] < mid:\n",
    "                        j -= 1\n",
    "                    cnt += neg2 - j\n",
    "                j = pos2\n",
    "                for x in reversed(nums1[pos1:]):\n",
    "                    while j < n2 and x * nums2[j] < mid:\n",
    "                        j += 1\n",
    "                    cnt += j - pos2\n",
    "            else:\n",
    "                j = n2 - 1\n",
    "                for x in reversed(nums1[:neg1 + 1]):\n",
    "                    while j >= pos2 and x * nums2[j] < mid:\n",
    "                        j -= 1\n",
    "                    cnt += n2 - j - 1\n",
    "                j = 0\n",
    "                for x in nums1[pos1:]:\n",
    "                    while j <= neg2 and x * nums2[j] < mid:\n",
    "                        j += 1\n",
    "                    cnt += j\n",
    "            if cnt >= k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "    n, m = len(nums1), len(nums2)\n",
    "    \n",
    "    def CountLessThan(upto: int):\n",
    "      got = 0\n",
    "      for x in nums1:\n",
    "        if x > 0:\n",
    "          got += bisect_right(nums2, upto // x)\n",
    "          # got += bisect_right(nums2, floor(upto // x))\n",
    "        elif x < 0:\n",
    "          got += m - bisect_left(nums2, -1 * (-upto // x))\n",
    "          # got += m - bisect_left(nums2, ceil(upto / x))\n",
    "        else:\n",
    "          got += 0 if upto < 0 else m\n",
    "      return got\n",
    "    \n",
    "    low, high = int(-1E10), int(1E10)\n",
    "    while low < high:\n",
    "      mid = (low + high) >> 1\n",
    "      got = CountLessThan(mid)\n",
    "      if got < k:\n",
    "        low = mid + 1\n",
    "      else:\n",
    "        high = mid\n",
    "    return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        def zz(x: int) -> bool:\n",
    "            res = 0\n",
    "            for a in nums1:\n",
    "                if a > 0:\n",
    "                    if a * nums2[0] > x: continue\n",
    "                    # res += bisect.bisect(nums2, x, key = lambda y: a * y)\n",
    "                    res += bisect.bisect(nums2, x // a)\n",
    "                    # left, right = 0, len(nums2) - 1\n",
    "                    # v = x // a\n",
    "                    # while left < right:\n",
    "                    #     m = (left + right + 1) >> 1\n",
    "                    #     # if a * nums2[m] <= x:\n",
    "                    #     if nums2[m] <= v:\n",
    "                    #         left = m\n",
    "                    #     else:\n",
    "                    #         right = m - 1\n",
    "                    # res += right + 1\n",
    "                elif a < 0:\n",
    "                    if a * nums2[-1] > x: continue\n",
    "                    res += len(nums2) - bisect.bisect_left(nums2, ceil(x / a))\n",
    "                    # left, right = 0, len(nums2) - 1\n",
    "                    # v = ceil(x / a)\n",
    "                    # while left < right:\n",
    "                    #     m = (left + right) >> 1\n",
    "                    #     # if a * nums2[m] <= x:\n",
    "                    #     #     right = m\n",
    "                    #     # else:\n",
    "                    #     #     left = m + 1\n",
    "                    #     if nums2[m] < v:\n",
    "                    #         left = m + 1\n",
    "                    #     else:\n",
    "                    #         right = m\n",
    "                    # res += len(nums2) - right\n",
    "                elif x >= 0:\n",
    "                    res += len(nums2)\n",
    "            return res >= k\n",
    "        \n",
    "        r = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))\n",
    "        l = -r\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if zz(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        def check(tgt):\n",
    "            cnt = 0\n",
    "            for num in nums2:\n",
    "                if num>0: # 正好等于tgt/num的也要算在内，因此用bisect_right\n",
    "                    cnt+=bisect_right(nums1,tgt/num)\n",
    "                elif num==0: # 除以0会RE，直接特判\n",
    "                    cnt+=len(nums1)*(tgt>=0) \n",
    "                else: # 注意此时用bisect_left，否则正好等于tgt/num的会被排除掉\n",
    "                    cnt+=len(nums1)-bisect_left(nums1,tgt/num)\n",
    "            return cnt\n",
    "        \n",
    "        mx = max(abs(nums1[0]),abs(nums1[-1]))*max(abs(nums2[0]),abs(nums2[-1])) #确定答案的可能范围\n",
    "        return bisect_left(range(-mx,mx+1),k,key=check)-mx #bisect_left输出的是下标，由于起点不是0，返回时要补差价\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        t = (nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[0], nums1[-1] * nums2[-1])\n",
    "        left, right = min(t), max(t)\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        neg1, pos1 = bisect_left(nums1, 0) - 1, bisect_left(nums1, 1)\n",
    "        neg2, pos2 = bisect_left(nums2, 0) - 1, bisect_left(nums2, 1)\n",
    "        cnt1, cnt2 = pos1 - neg1 - 1, pos2 - neg2 - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            cnt = cnt1 * n2 + (n1 - cnt1) * cnt2 if mid > 0 else 0\n",
    "            if mid >= 0:\n",
    "                cnt += (neg1 + 1) * (n2 - pos2) + (n1 - pos1) * (neg2 + 1)\n",
    "                j = neg2\n",
    "                for x in nums1[:neg1 + 1]:\n",
    "                    while j >= 0 and x * nums2[j] < mid:\n",
    "                        j -= 1\n",
    "                    cnt += neg2 - j\n",
    "                j = pos2\n",
    "                for x in reversed(nums1[pos1:]):\n",
    "                    while j < n2 and x * nums2[j] < mid:\n",
    "                        j += 1\n",
    "                    cnt += j - pos2\n",
    "            else:\n",
    "                j = n2 - 1\n",
    "                for x in reversed(nums1[:neg1 + 1]):\n",
    "                    while j >= pos2 and x * nums2[j] < mid:\n",
    "                        j -= 1\n",
    "                    cnt += n2 - j - 1\n",
    "                j = 0\n",
    "                for x in nums1[pos1:]:\n",
    "                    while j <= neg2 and x * nums2[j] < mid:\n",
    "                        j += 1\n",
    "                    cnt += j\n",
    "            if cnt >= k:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        m,n=len(nums1),len(nums2)\n",
    "\n",
    "        def check(mid):\n",
    "            cnt=0            \n",
    "            for v  in nums1:\n",
    "                ans=0\n",
    "                if v==0:\n",
    "                    ans=n*int(mid>=0)\n",
    "                else:\n",
    "                    # 正负号只和分母有关\n",
    "                    u=mid/v\n",
    "                    if v>0:\n",
    "                        ans=bisect_right(nums2,u)\n",
    "                    else:\n",
    "                        ans=n-bisect_left(nums2,u)\n",
    "                # print(v,u,mid,ans)\n",
    "                cnt+=ans\n",
    "            return cnt<k\n",
    "\n",
    "        # 枚举两个数的乘积\n",
    "        l,r=-10**10,10**10\n",
    "        while l<r:\n",
    "            # 找恰好满足条件的最小值\n",
    "            mid=l+r>>1\n",
    "            if check(mid):\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        def zz(x: int) -> bool:\n",
    "            res = 0\n",
    "            for a in nums1:\n",
    "                if a > 0:\n",
    "                    if a * nums2[0] > x: continue\n",
    "                    res += bisect.bisect(nums2, x, key = lambda y: a * y)\n",
    "                    # res += bisect.bisect(nums2, x // a)\n",
    "                    # left, right = 0, len(nums2) - 1\n",
    "                    # v = x // a\n",
    "                    # while left < right:\n",
    "                    #     m = (left + right + 1) >> 1\n",
    "                    #     # if a * nums2[m] <= x:\n",
    "                    #     if nums2[m] <= v:\n",
    "                    #         left = m\n",
    "                    #     else:\n",
    "                    #         right = m - 1\n",
    "                    # res += right + 1\n",
    "                elif a < 0:\n",
    "                    if a * nums2[-1] > x: continue\n",
    "                    res += len(nums2) - bisect.bisect_left(nums2, ceil(x / a))\n",
    "                    # left, right = 0, len(nums2) - 1\n",
    "                    # v = ceil(x / a)\n",
    "                    # while left < right:\n",
    "                    #     m = (left + right) >> 1\n",
    "                    #     # if a * nums2[m] <= x:\n",
    "                    #     #     right = m\n",
    "                    #     # else:\n",
    "                    #     #     left = m + 1\n",
    "                    #     if nums2[m] < v:\n",
    "                    #         left = m + 1\n",
    "                    #     else:\n",
    "                    #         right = m\n",
    "                    # res += len(nums2) - right\n",
    "                elif x >= 0:\n",
    "                    res += len(nums2)\n",
    "            return res >= k\n",
    "        \n",
    "        r = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))\n",
    "        l = -r\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if zz(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        pos = []\n",
    "        neg = []\n",
    "        for n in nums2:\n",
    "            if n >= 0:\n",
    "                pos.append(n)\n",
    "            else:\n",
    "                neg.append(n)\n",
    "        left = min(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                   nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        right = max(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                    nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        while left < right:\n",
    "            used = 0\n",
    "            mid = (left+right)//2\n",
    "            for n in nums1:\n",
    "                if n > 0:\n",
    "                    used += bisect_right(pos, mid//n)\n",
    "                    used += bisect_right(neg, mid//n)\n",
    "                elif n < 0:\n",
    "                    used += len(pos)-bisect_left(pos, mid //\n",
    "                                                 n+(1 if mid % n else 0))\n",
    "                    used += len(neg)-bisect_left(neg, mid //\n",
    "                                                 n+(1 if mid % n else 0))\n",
    "                else:\n",
    "                    if mid >= 0:\n",
    "                        used += len(pos)+len(neg)\n",
    "                    else:\n",
    "                        used += 0\n",
    "            if used < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        def check(tgt):\n",
    "            cnt = 0\n",
    "            for num in nums2:\n",
    "                if num>0: # 正好等于tgt/num的也要算在内，因此用bisect_right\n",
    "                    cnt+=bisect_right(nums1,tgt/num)\n",
    "                elif num==0: # 除以0会RE，直接特判\n",
    "                    cnt+=len(nums1)*(tgt>=0) \n",
    "                else: # 注意此时用bisect_left，否则正好等于tgt/num的会被排除掉\n",
    "                    cnt+=len(nums1)-bisect_left(nums1,tgt/num)\n",
    "            return cnt\n",
    "        \n",
    "        mx = max(abs(nums1[0]),abs(nums1[-1]))*max(abs(nums2[0]),abs(nums2[-1])) #确定答案的可能范围\n",
    "        return bisect_left(range(-mx,mx+1),k,key=check)-mx #bisect_left输出的是下标，由于起点不是0，返回时要补差价\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        m,n=len(nums1),len(nums2)\n",
    "\n",
    "\n",
    "        def check(mid):\n",
    "            cnt=0\n",
    "            \n",
    "            for v  in nums1:\n",
    "                ans=0\n",
    "                if v==0:\n",
    "                    ans=n*int(mid>=0)\n",
    "                else:\n",
    "                    u=mid/v\n",
    "                    if v>0:\n",
    "                        ans=bisect_right(nums2,u)\n",
    "                    else:\n",
    "                        ans=n-bisect_left(nums2,u)\n",
    "                # print(v,u,mid,ans)\n",
    "                cnt+=ans\n",
    "            return cnt<k\n",
    "\n",
    "        # 枚举两个数的乘积\n",
    "        l,r=-10**10,10**10\n",
    "        while l<r:\n",
    "            mid=l+r>>1\n",
    "            if check(mid):\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for v in nums1:\n",
    "                if v == 0:\n",
    "                    if x >= 0: cnt += len(nums2)\n",
    "                elif v > 0:\n",
    "                    p = bisect_right(nums2, math.floor(x/v))\n",
    "                    cnt += p \n",
    "                else:\n",
    "                    p = bisect_left(nums2, math.ceil(x/v))\n",
    "                    cnt += len(nums2) - p \n",
    "            return cnt >= k\n",
    "\n",
    "        l = min(nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[-1], nums1[-1] * nums2[0])\n",
    "        r = max(nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[-1], nums1[-1] * nums2[0])\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid): r = mid \n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "二分答案的题，和乘法表的题目一样，子问题是，乘积不超过 x 能找到多少对来完成，\n",
    "那么最小的 x 且满足至少有 k 对的情况就是答案。\n",
    "\n",
    "注意数字不是正数，不等号的处理。如果是 0，那么不等式不是一元一次不等式，\n",
    "如果是负数，不等号要反向，另外还要注意 python 除法的取整问题。\n",
    "python 中的 // 是向下取整，但是向上取整，为了方便，直接浮点除法 + math.ceil 调用实现。\n",
    "'''\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if len(nums1) >= len(nums2): nums1, nums2 = nums2, nums1  # nums2取长的\n",
    "        \n",
    "        a, b, c, d = nums1[0] * nums2[0], nums1[0] * nums2[-1], nums1[-1] * nums2[-1], nums1[-1] * nums2[0]\n",
    "        mn, mx = min(a, b, c, d), max(a, b, c, d)\n",
    "        while mn < mx:\n",
    "            mid = (mn + mx) >> 1\n",
    "            cnt = 0\n",
    "            for num in nums1:\n",
    "                if num > 0:\n",
    "                    cnt += bisect.bisect_right(nums2, mid // num)\n",
    "                elif num == 0:\n",
    "                    cnt += len(nums2) if mid >= 0 else 0\n",
    "                else:\n",
    "                    cnt += len(nums2) - bisect.bisect_left(nums2, math.ceil(mid / num))\n",
    "            if cnt < k:\n",
    "                mn = mid + 1\n",
    "            else:\n",
    "                mx = mid\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        def check(tgt):\n",
    "            cnt = 0\n",
    "            for num in nums2:\n",
    "                if num>0: \n",
    "                    cnt+=bisect_right(nums1,tgt/num)\n",
    "                elif num==0:\n",
    "                    cnt+=len(nums1)*(tgt>=0) \n",
    "                else:\n",
    "                    cnt+=len(nums1)-bisect_left(nums1,tgt/num)\n",
    "            return cnt\n",
    "        \n",
    "        mx = max(abs(nums1[0]),abs(nums1[-1]))*max(abs(nums2[0]),abs(nums2[-1]))\n",
    "        return bisect_left(range(-mx,mx+1),k,key=check)-mx "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        def check(tgt):\n",
    "            cnt = 0\n",
    "            for num in nums2:\n",
    "                if num>0: # 正好等于tgt/num的也要算在内，因此用bisect_right\n",
    "                    cnt+=bisect_right(nums1,tgt/num)\n",
    "                elif num==0: # 除以0会RE，直接特判\n",
    "                    cnt+=len(nums1)*(tgt>=0) \n",
    "                else: # 注意此时用bisect_left，否则正好等于tgt/num的会被排除掉\n",
    "                    cnt+=len(nums1)-bisect_left(nums1,tgt/num)\n",
    "            return cnt\n",
    "        \n",
    "        mx = max(abs(nums1[0]),abs(nums1[-1]))*max(abs(nums2[0]),abs(nums2[-1])) #确定答案的可能范围\n",
    "        return bisect_left(range(-mx,mx+1),k,key=check)-mx #bisect_left输出的是下标，由于起点不是0，返回时要补差价"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "\n",
    "        def check(tgt):\n",
    "            cnt = 0\n",
    "            for num in nums2:\n",
    "                if num > 0:\n",
    "                    cnt += bisect_right(nums1, tgt / num)\n",
    "                elif num == 0:\n",
    "                    cnt += len(nums1) * (tgt >= 0)\n",
    "                else:\n",
    "                    cnt += len(nums1) - bisect_left(nums1, tgt / num)\n",
    "            return cnt\n",
    "\n",
    "        mx = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))\n",
    "        return bisect_left(range(-mx, mx + 1), k, key=check) - mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "    n, m = len(nums1), len(nums2)\n",
    "    pos1, neg1 = [], []\n",
    "    pos2, neg2 = [], []\n",
    "    for x in nums1:\n",
    "      if x >= 0:\n",
    "        pos1.append(x)\n",
    "      elif x < 0:\n",
    "        neg1.append(x)\n",
    "    for x in nums2:\n",
    "      if x >= 0:\n",
    "        pos2.append(x)\n",
    "      elif x < 0:\n",
    "        neg2.append(x)\n",
    "    def CountLessThan(upto: int):\n",
    "      got = 0\n",
    "      # x1 < 0, x2 < 0\n",
    "      ptr = len(neg2) - 1\n",
    "      for x in neg1:\n",
    "        while ptr >= 0 and x * neg2[ptr] <= upto:\n",
    "          ptr -= 1\n",
    "        got += len(neg2) - 1 - ptr\n",
    "      # x1 > 0, x2 > 0\n",
    "      ptr = len(pos2) - 1\n",
    "      for x in pos1:\n",
    "        while ptr >= 0 and x * pos2[ptr] > upto:\n",
    "          ptr -= 1\n",
    "        got += ptr + 1\n",
    "      # x1 < 0, x2 > 0\n",
    "      ptr = 0\n",
    "      for x in neg1:\n",
    "        while ptr < len(pos2) and x * pos2[ptr] > upto:\n",
    "          ptr += 1\n",
    "        got += len(pos2) - ptr\n",
    "      # x1 > 0, x2 < 0\n",
    "      ptr = 0\n",
    "      for x in pos1:\n",
    "        while ptr < len(neg2) and x * neg2[ptr] <= upto:\n",
    "          ptr += 1\n",
    "        got += ptr\n",
    "      # print(upto, got)\n",
    "      return got\n",
    "    \n",
    "    low, high = int(-1E10), int(1E10)\n",
    "    while low < high:\n",
    "      mid = (low + high) >> 1\n",
    "      got = CountLessThan(mid)\n",
    "      if got < k:\n",
    "        low = mid + 1\n",
    "      else:\n",
    "        high = mid\n",
    "    return low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        p10 = bisect.bisect_left(nums1, 0)\n",
    "        p11 = bisect.bisect_left(nums1, 1)\n",
    "        p20 = bisect.bisect_left(nums2, 0)\n",
    "        p21 = bisect.bisect_left(nums2, 1)\n",
    "\n",
    "        neg = p10 * (n2 - p21) + p20 * (n1 - p11)\n",
    "        pos = p10 * p20 + (n1 - p11) * (n2 - p21)\n",
    "        zero = n1 * n2 - neg - pos\n",
    "\n",
    "        pos1, pos2 = nums1[p11:], nums2[p21:]\n",
    "        neg1, neg2 = nums1[:p10], nums2[:p20]\n",
    "        \n",
    "        for i in range(len(neg2)):\n",
    "            neg2[i] = -neg2[i]\n",
    "        \n",
    "        neg2.sort()\n",
    "        if k <= neg:\n",
    "            k = neg - k + 1\n",
    "            left, right = -1, int(1e10)\n",
    "            while left + 1 < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                cnt = 0\n",
    "                for v in pos1:\n",
    "                    cnt += bisect.bisect_left(neg2, mid // v + 1)\n",
    "                for v in neg1:\n",
    "                    cnt += bisect.bisect_left(pos2, -mid // v + 1)\n",
    "                if cnt >= k:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            return -right\n",
    "\n",
    "        if k <= neg + zero:\n",
    "            return 0\n",
    "\n",
    "        k -= neg + zero\n",
    "        left, right = -1, int(1e10)\n",
    "        while left + 1 < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            cnt = 0\n",
    "            for v in pos1:\n",
    "                cnt += bisect.bisect_left(pos2, mid // v + 1)\n",
    "            for v in neg1:\n",
    "                cnt += bisect.bisect_left(neg2, -mid // v + 1)\n",
    "            if cnt >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countUsedPairs(self, mid, pos1, neg1, pos2, neg2):\n",
    "        used = 0\n",
    "        i = 0\n",
    "        j = len(pos2) - 1\n",
    "        while i < len(pos1):\n",
    "            while j >= 0 and pos1[i] * pos2[j] > mid:\n",
    "                j -= 1\n",
    "            used += j + 1\n",
    "            i += 1\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(neg1):\n",
    "            while j < len(pos2) and neg1[i] * pos2[j] > mid:\n",
    "                j += 1\n",
    "            used += len(pos2) - j\n",
    "            i += 1\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(pos1):\n",
    "            while j < len(neg2) and pos1[i] * neg2[j] <= mid:\n",
    "                j += 1\n",
    "            used += j\n",
    "            i += 1\n",
    "        i = 0\n",
    "        j = len(neg2) - 1\n",
    "        while i < len(neg1):\n",
    "            while j >= 0 and neg1[i] * neg2[j] <= mid:\n",
    "                j -= 1\n",
    "            used += len(neg2) - 1 - j\n",
    "            i += 1\n",
    "        return used\n",
    "\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if len(nums1) > len(nums2):\n",
    "            return self.kthSmallestProduct(nums2, nums1, k)\n",
    "        pos1 = []\n",
    "        neg1 = []\n",
    "        pos2 = []\n",
    "        neg2 = []\n",
    "        for n in nums1:\n",
    "            if n >= 0:\n",
    "                pos1.append(n)\n",
    "            else:\n",
    "                neg1.append(n)\n",
    "        for n in nums2:\n",
    "            if n >= 0:\n",
    "                pos2.append(n)\n",
    "            else:\n",
    "                neg2.append(n)\n",
    "        left = min(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                   nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        right = max(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                    nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        while left < right:\n",
    "            used = 0\n",
    "            mid = (left+right)//2\n",
    "            used = self.countUsedPairs(mid, pos1, neg1, pos2, neg2)\n",
    "            if used < k:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        if len(nums1) > len(nums2):\n",
    "            return self.kthSmallestProduct(nums2, nums1, k)\n",
    "        pos = []\n",
    "        neg = []\n",
    "        for n in nums2:\n",
    "            if n >= 0:\n",
    "                pos.append(n)\n",
    "            else:\n",
    "                neg.append(n)\n",
    "        left = min(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                   nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        right = max(nums1[0]*nums2[0], nums1[0]*nums2[-1],\n",
    "                    nums1[-1]*nums2[0], nums1[-1]*nums2[-1])\n",
    "        while left < right:\n",
    "            used = 0\n",
    "            mid = (left+right)//2\n",
    "            for n in nums1:\n",
    "                if n > 0:\n",
    "                    used += bisect_right(pos, mid//n)\n",
    "                    used += bisect_right(neg, mid//n)\n",
    "                elif n < 0:\n",
    "                    used += len(pos)-bisect_left(pos, mid //\n",
    "                                                 n+(1 if mid % n else 0))\n",
    "                    used += len(neg)-bisect_left(neg, mid //\n",
    "                                                 n+(1 if mid % n else 0))\n",
    "                else:\n",
    "                    if mid >= 0:\n",
    "                        used += len(pos)+len(neg)\n",
    "                    else:\n",
    "                        used += 0\n",
    "                if used >= k:\n",
    "                    break\n",
    "            if used < k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def kthSmallestProduct(self,nums1, nums2, K):\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        p10 = bisect.bisect_left(nums1, 0)\n",
    "        p11 = bisect.bisect_left(nums1, 1)\n",
    "        p20 = bisect.bisect_left(nums2, 0)\n",
    "        p21 = bisect.bisect_left(nums2, 1)\n",
    "\n",
    "        neg = p10*(n2-p21) + p20*(n1-p11)  # 负数乘积个数\n",
    "        pos = p10*p20 + (n1-p11)*(n2-p21)  # 正数乘积个数\n",
    "        zero = n1*n2 - neg - pos  # 乘积为 0 的个数\n",
    "\n",
    "        pos1, pos2 = nums1[p11:], nums2[p21:]\n",
    "        neg1, neg2 = nums1[:p10], nums2[:p20]\n",
    "        neg2 = [-x for x in neg2][::-1]\n",
    "\n",
    "        k = K\n",
    "        if k <= neg:\n",
    "            k = neg - k + 1\n",
    "            left, right = -10**10, 10**10\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                cnt = sum(bisect.bisect_right(neg2, mid//v) for v in pos1) + sum(bisect.bisect_right(pos2, -mid//v) for v in neg1)\n",
    "                if cnt >= k:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return -left\n",
    "\n",
    "        if k <= neg + zero:\n",
    "            return 0\n",
    "\n",
    "        k -= neg + zero\n",
    "        left, right = -10**10, 10**10\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            cnt = sum(bisect.bisect_right(pos2, mid//v) for v in pos1) + sum(bisect.bisect_right(neg2, -mid//v) for v in neg1)\n",
    "            if cnt >= k:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n",
    "        def getCnt(m, n1, n2):\n",
    "            if not n1 or not n2 :\n",
    "                return 0\n",
    "            cnt = 0\n",
    "            j = len(n2)-1\n",
    "            for i in range(len(n1)):\n",
    "                while n1[i] * n2[j] > m:\n",
    "                    j -= 1\n",
    "                    if j < 0:\n",
    "                        return cnt\n",
    "                cnt += j+1\n",
    "            return cnt\n",
    "\n",
    "        def getAns(n1, n2, m1, m2, target):\n",
    "            l, r = inf, 0\n",
    "            if n1 and n2:\n",
    "                l = min(n1[0]*n2[0], l)\n",
    "                r = max(n1[-1]*n2[-1], r)\n",
    "            if m1 and m2:\n",
    "                l = min(m1[0]*m2[0], l)\n",
    "                r = max(m1[-1]*m2[-1], r)\n",
    "            while l <= r:\n",
    "                m = (l+r)//2\n",
    "                if getCnt(m, n1, n2) + getCnt(m, m1, m2) < target:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m-1\n",
    "            return l\n",
    "\n",
    "        # 1: 负,2: 零,3: 正\n",
    "        n1, n2, n3 = [], [], []\n",
    "        m1, m2, m3 = [], [], []\n",
    "        for n in nums1:\n",
    "            if n == 0:\n",
    "                n2.append(n)\n",
    "            elif n < 0:\n",
    "                n1.append(-n)\n",
    "            else:\n",
    "                n3.append(n)\n",
    "        for n in nums2:\n",
    "            if n == 0:\n",
    "                m2.append(n)\n",
    "            elif n < 0:\n",
    "                m1.append(-n)\n",
    "            else:\n",
    "                m3.append(n)\n",
    "        cnt1 = len(n1)*len(m3)+len(n3)*len(m1)\n",
    "        cnt2 = len(n2)*len(nums2)+len(nums1)*len(m2)-len(n2)*len(m2)\n",
    "        cnt3 = len(n1)*len(m1)+len(n3)*len(m3)\n",
    "        n1.reverse()\n",
    "        m1.reverse()\n",
    "        if k <= cnt1:\n",
    "            return -getAns(n1,m3,n3,m1,cnt1-k+1)\n",
    "        elif k <= cnt1+cnt2:\n",
    "            return 0\n",
    "        else:\n",
    "            return getAns(n1,m1,n3,m3,k-cnt1-cnt2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
